package com.leetcode.partition7;

/**
 * @author `RKC`
 * @date 2021/9/30 20:05
 */
public class LC684冗余连接 {

    public static int[] findRedundantConnection(int[][] edges) {
        return unionFind(edges);
    }

    private static int[] unionFind(int[][] edges) {
        //一个无环无向连通图的节点数等于边数加1
        int[] parent = new int[edges.length + 1];
        for (int i = 1; i <= edges.length; i++) parent[i] = i;
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            if (find(parent, x) != find(parent, y)) {
                union(parent, x, y);
            } else {
                return edge;        //成环，直接返回
            }
        }
        return new int[0];
    }

    private static int find(int[] parent, int x) {
        if (x == parent[x]) return x;
        return find(parent, parent[x]);
    }

    private static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x), rootY = find(parent, y);
        if (rootX != rootY) parent[rootY] = rootX;
    }
}
